Ban đầu, Dinh cô chỉ là một ngôi miếu nhỏ đơn sơ, được lập ra vào cuối thế kỷ 18 (không rõ năm) để thờ một cô gái trẻ tên là Lê Thị Hồng (tục là Thị Cách).

Tương truyền, cô là người ở Tam Quan (Bình Định)[3]. Trên đường đi ra biển [4] thì bị lâm nạn và xác trôi dạt vào Hòn Hang (gần khu di tích Dinh Cô bây giờ). Lúc ấy, cô chỉ vừa sang tuổi 16. Thương tiếc, người dân địa phương lúc bấy giờ đã đem xác cô vào chôn cất trên đồi Cô Sơn. Từ đó cô luôn hiển linh mộng báo điềm lành, diệt trừ dịch bệnh, độ trì bá tánh, phù trợ ngư dân…nên dân trong vùng tôn xưng cô là "Long Hải Thần Nữ Bảo An Chánh Trực Nương Nương Chi Thần".

Năm 1930, ngư dân Long Hải đã dời miếu thờ lên đồi Kỳ Vân cho đến ngày nay. Năm 1987, Dinh Cô được xây dựng và trùng tu lớn sau khi bị hỏa hoạn. Năm 2006 - 2007, Dinh Cô lại được trùng tu.